Many different compression algorithms have been proposed for compressing cache lines in caches. In general, these algorithms are suitable for compressing program data because such data is typically highly structured. For example, program data often includes large strings of repetitive data, similarly valued numbers adjacent to one another, and values that repeat across cache lines when the data is stored in a cache. Compressors implementing such compression algorithms reduce the storage space required for cache lines when they are able to replace the repetitive data with a more succinct representation.
While these compression algorithms can also be employed to compress a cache structure's tags, they often yield inconsistent compression ratios, which results in great variability in the size of the compressed tags. This variability complicates the associated hardware cache design and verification since the tag arrays need to be able to store and retrieve variable length compressed tags. By contrast, techniques that yield a consistent compression ratio are simpler to implement since there is only a single size of compressed tag. Furthermore, when dealing with caching, especially hardware-based caching, the latency of the compression algorithm often dictates the feasibility of its implementation for different levels of the cache hierarchy. Compression technology needs to operate within the latency threshold of the underlying cache so that its costs are hidden from the critical path of the processor's execution. Simpler compression techniques can be more easily implemented subject to these latency constraints and in hardware implementations typically require less power and area.
In the following description, the use of the same reference numerals in different drawings indicates similar or identical items. Unless otherwise noted, the word “coupled” and its associated verb forms include both direct connection and indirect electrical connection by means known in the art, and unless otherwise noted any description of direct connection implies alternate embodiments using suitable forms of indirect electrical connection as well.